The present invention relates to the field of computers. More specifically, the present invention relates to concurrent access of data structures.
Synchronization mechanisms are utilized to implement concurrent access of an object. Some synchronization mechanisms include locking and transactional synchronization. Programs written in concurrent object-oriented languages frequently rely on locking for synchronization. A number of efficient mechanisms have been developed for object-level locking, such as described in An Efficient Meta-lock for Implementing Ubiquitous Synchronization by O. Agesen, D. Detlefs, A. Garthwaite, R. Knippel, Y. S. Ramakrishna, and D. White, which are used in the EVM Java® Virtual Machine, the Thin-Locks described in Thin Locks: Featherweight Synchronization for Java by D. F. Bacon, R. B. Konuru, C. Murthy, and M. J. Serrano, and the Relaxed-Locks described in Implementing Fast Java Monitors with Relaxed Locks by D. Dice. Recently, there has been interest in alternative synchronization structures, including transactional synchronization, such as described in Transactional Memory: Architectural Support for Lock-Free Data Structures by M. Herlihy and J. E. B. Moss. A transaction is a sequence of method calls that is executed atomically, that is, transactions appear to execute sequentially, in a one-at-a-time order. As a programming tool, transactions provide atomicity like critical sections, but without their added complexities.
Software transactional synchronization mechanisms have been proposed at the application level (as a collection of libraries) and at the level of individual memory accesses. However, an approach based on libraries can be cumbersome for a programmer. Low-level memory-access approaches that may benefit C programmers are poorly suited for object-oriented languages because each memory reference requires multiple low-level memory references which in turn take several expensive synchronization instructions each.